﻿#light
module NewKDTree

open System
open Microsoft.Xna.Framework
open System.Collections
open Structures

type KDTree =
    |Branch of BoundingBox * X3dModel list * KDTree * KDTree
    |Leaf of BoundingBox * X3dModel list

let split_list lst n = 
    let before = Seq.take n (Seq.ofArray lst)
    let after = Seq.skip n (Seq.ofArray lst)
    (before,after)

let split (models:X3dModel List) =
    let modelsArray = List.toArray models
    let vec3Model (model:X3dModel) =
        model.Vertices |> Array.map (fun x -> (Vector3.Transform(x.Position,model.World)), model)
    let V3Array = 
        Array.concat (Array.map vec3Model modelsArray)
    let variances (pts:(Vector3 * X3dModel) array) = 
         let mean (el:(float32 [])) = 
            (Array.sum el) / (float32)el.Length
         let variance (el:(float32 []))= 
            let media = mean el
            (Array.sum (Array.map (fun n -> pown (n-media) 2) el) / (float32)el.Length)
         let (points,y) = Array.unzip pts
         (variance (points |> Array.map (fun x -> x.X)),
          variance (points |> Array.map (fun x -> x.Y)),
          variance (points |> Array.map (fun x -> x.Z)))         
    let (vx,vy,vz) = variances V3Array
    let (pt_before,pt_after) =
        if ((vx>=vy)&&(vx>=vz)) then 
            split_list (Array.sortBy (fun (x:Vector3,y) -> x.X) V3Array) (V3Array.Length/2)
            else if (vy>=vx)&&(vy>=vz) then 
                    split_list (Array.sortBy (fun (x:Vector3,y) -> x.Y) V3Array) (V3Array.Length/2)
                 else
                    split_list (Array.sortBy (fun (x:Vector3,y) -> x.Z) V3Array) (V3Array.Length/2)
    let (before,after) = 
        (Set.ofSeq (Seq.distinct (Seq.map (fun (x,y) -> y) pt_before)),
         Set.ofSeq (Seq.distinct (Seq.map (fun (x,y) -> y) pt_after)))
    let between = Set.intersect before after
    (Set.toList between,
     Set.toList before,
     Set.toList after)    
let rec build (models:X3dModel list) =
    let modelsArray = Array.ofList models
    let pts = modelsArray 
                |> Array.map (fun x -> x.Vertices)
                |> Array.concat
                |> Array.map (fun x -> x.Position)
    let (between,left,right) = 
        if (pts.Length < 1000) then (models,[],[])
        else split models
    match (between,left,right) with
    |([],[],[]) -> Leaf (new BoundingBox(),[])
    |(b,[],[]) -> Leaf (BoundingBox.CreateFromPoints(pts),b)
    |(b,l,r) -> Branch (BoundingBox.CreateFromPoints(pts),b,build (l),build (r))

let rec intersectBB root (camera:BoundingFrustum) = match root with
                                                    |Leaf(bb,[]) -> []
                                                    |Leaf(bb,lst) -> if (camera.Intersects(bb)) then lst
                                                                        else []
                                                    |Branch(bb,lst,left,right) -> if (camera.Intersects(bb)) then lst@(intersectBB left camera)@(intersectBB right camera)
                                                                                    else (intersectBB left camera)@(intersectBB right camera)
